﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>


//数据结构
//  不仅能储存数据，还要能管理数据
//数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数
//据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构，
//如：线性表、树、图、哈希等


//
//算法
//算法(Algorithm) :就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为
//输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果
//


//时间复杂度为n的平方
//void rotate(int* nums, int numsSize, int k) {
//	while (k--)
//	{
//		int end = nums[numsSize - 1];
//		for (int i = numsSize - 1; i > 0; i--)
//		{
//			nums[i] = nums[i - 1];
//		}
//		nums[0] = end;
//	}
//}



//时间复杂度主要衡量⼀个算法的运⾏快慢，
//⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间


//时间复杂度
//定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。
//    N为影响时间复杂度的输入条件

//时间复杂度为n的平方
// ++cuont的运行次数 T(N) = N*N + 2*N + 10
// 时间复杂度 = 每条语句执行的时间 * 每条语句的执行次数
//void Func1(int N)
//{
//	int count = 0;
//	for (int i = 0; i < N; ++i)
//	{
//		for (int j = 0; j < N; ++j)
//		{
//			++count;//这个是关键指令
//		}
//	}
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	}
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//}


//
//计算程序能代表增⻓量
//级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。



//时间复杂度只能用来表示输入条件对时间的影响趋势



//推导⼤O阶规则
//1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，
//低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
//2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
//对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
//3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。


// 计算Func2的时间复杂度？
// O(N)
//void Func2(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	}
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}



// 计算Func3的时间复杂度？
//   O(n)
//void Func3(int N, int M)
//{
//	int count = 0;
//	for (int k = 0; k < M; ++k)
//	{
//		++count;//  M次
//	}
//	for (int k = 0; k < N; ++
//		k)
//	{
//		++count;//N次
//	}
//	printf("%d\n", count);
//}



// 计算Func4的时间复杂度？
// O(1) 这里的1 不是执行一次，而是表示常数
//void Func4(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 100; ++k)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}



// 计算strchr的时间复杂度？
// O(N)
//const char* strchr(const char* str, int character)
//{
//	const char* p_begin = str;
//	while (*p_begin != character)
//	{
//		if (*p_begin == '\0')
//			return NULL;
//		p_begin++;
//	}
//	return p_begin;
//}



//
//通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
//最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
//平均情况：任意输⼊规模的期望运⾏次数
//最好情况：任意输⼊规模的最⼩运⾏次数(下界)
//⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。




// 计算BubbleSort的时间复杂度？
// O(N^2)
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)//n
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}


//    O(long n)  建议使用这种
//void func5(int n)
//{
//	int cnt = 1;
//	while (cnt < n)
//	{
//		cnt *= 2;
//	}
//}


//注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰
//当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不
//写，即可以表⽰为 log n
//不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n


// 计算阶乘递归Fac的时间复杂度？
//  O(N)
long long Fac(size_t N)
{
	if (0 == N)
	{
		return 1;
	}
	return Fac(N - 1) * N;
}